/*
    8n皇后(回溯算法)
 */
class quenn{
    private int max = 8;
    private int result[] = new int[max];

    public void resolve(int n){
        if (n == max){
            print();
            return;
        }

        for (int i = 0 ;i < max ; i++){
            result[n] = i;
            if (judge(n)){ // 判断皇后是否冲突
                resolve(n+1);
            }
        }
    }

    public boolean judge(int n){
        for (int i = 0 ; i < n ; i++){
            if (result[i]==result[n] || Math.abs(result[n]-result[i])==Math.abs(n-i)){ // 列向判断 || 斜向判断
                return false;
            }
        }
        return true;
    }

    public void print(){
        for (int i=0;i<max;i++){
            System.out.print((result[i]+1)+" ");//由于数组是从0计数的，为了方便阅读+1
        }
        System.out.println();
    }
}

public class Queen8n {
    public static void main(String[] args) {
        quenn q = new quenn();
        q.resolve(0);
    }
}
